package leetcode101.bit_operation;

import java.util.Arrays;

/**
 * @author Synhard
 * @version 1.0
 * @class Code11
 * @description 260. 只出现一次的数字 III
 * 给定一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。 找出只出现一次的那两个元素。你可以按 任意顺序 返回答案。
 *
 * 进阶：你的算法应该具有线性时间复杂度。你能否仅使用常数空间复杂度来实现？
 *
 *
 * 示例 1：
 *
 * 输入：nums = [1,2,1,3,2,5]
 * 输出：[3,5]
 * 解释：[5,3] 也是有效的答案。
 * 示例 2：
 *
 * 输入：nums = [-1,0]
 * 输出：[-1,0]
 * 示例 3：
 *
 * 输入：nums = [0,1]
 * 输出：[1,0]
 * 提示：
 *
 * 2 <= nums.length <= 3 * 104
 * -231 <= nums[i] <= 231 - 1
 * 除两个只出现一次的整数外，nums 中的其他数字都出现两次
 * 
 * @tel 13001321080
 * @email 823436512@qq.com
 * @date 2021-05-07 15:10
 */
public class Code11 {
    public static void main(String[] args) {
        int[] nums = new int[]{1,2,1,3,2,5};
        System.out.println(Arrays.toString(singleNumber(nums)));
    }

    public static int[] singleNumber(int[] nums) {
        int xor = 0;
        for (int i : nums) {
            xor ^= i;
        }

        int pos = 1;
        while ((1 & xor) != 1) {
            xor >>= 1;
            pos <<= 1;
        }

        int a = 0, b = 0;
        for (int i : nums) {
            if ((i & pos) != 0) {
                a ^= i;
            } else {
                b ^= i;
            }
        }

        return new int[]{a, b};
    }
}
/*
首先将所有的数据异或，那么得到的结果相当于仅出现一次的两个数字异或的结果
然后按照异或的结果，找到两个数字上某一个不同的位
按照这个不同的位将所有的数字分为两组
这两组可以保证两个只出现一次的数字分在了两个不同的组
其他相同的数字会被分到某一个组中
 */